package com.zhanghp.class01;

import static com.zhanghp.utils.CommonUtils.TEST_COUNT;
import static java.lang.Math.random;

/**
 * 2. 如何用a~b的随机函数加工出c~d的随机函数
 * <ul>
 *     <li>利用等概率返回[a,b]，算出0,1等概率返回</li>
 *     <li>处理[c,d]所需二进制的位数</li>
 *     <li>将上面两个步骤结合，生成等概率返回的[c,d]</li>
 * </ul>
 *
 * @author zhanghp
 * @date 2023/7/31 12:45
 */
public class Code07_RandToRand2 {
    public static void main(String[] args) {
//        verifyFacade(1, 5, 3, 9);
//        int from = 0;
//        int to = 8;
//        int range = to -from;
//        int num = 1;
//        // 求0～range需要几个2进制位
//        while ((1 << num) - 1 < range) {
//            num++;
//        }
//        System.out.println(num);
//        verifyBinaryShift(10);
//        verifyZuoBinaryShift(1, 10);
//
//        printDivingLine();
//        verifyZuoFacade(1,5,3,5);
//        printDivingLine();
        verifyZuoBinaryShift(1, 6);
    }


    /**
     * Me -------------------------------------------------->
     */
    /**
     * 1. 利用[a,b]等概率返回0,1
     * <ul>
     *     <li>
     *         偶数情况可直接返回
     *     </li>
     *     <li>
     *         奇数情况判断
     *     </li>
     * </ul>
     *
     * @return [a, b]
     */
    private static int handleRandBox(RandBox randBox) {
        int min = randBox.min;
        int max = randBox.max;
        int middle = min + ((max - min) + 1) / 2;
        int num;
        // 奇数判断
        do {
            num = randBox.blackBoxAToB();
        } while (((max - min + 1) % 2 != 0) && num == middle);
        return num < middle ? 0 : 1;
    }

    /**
     * 2. 获取[c,d]所需移位的位数
     *
     * @param desTo 目标结束值
     * @return 移位
     */
    private static int binaryShift(int desTo) {
        int offset = 0;
        // 为什么这么能算出所需移位的数
        // 就比如 8 4 2 1 ，当前以移位的数值永远大于前几位的和
        // 所以当比较时，max值永远不会大于他的下一位移位
        // ex: max=6 移位比较时，1 2 4 8挨个比较，当不再小于max时也就是8就会跳出
        // 当移位算值时，用小于8的位数4，而不是小于等于
        // ex2： max = 8时， 8<8 = false，还会在加一次移位，所以不必担心临界值问题（当为8时移位会少一位的问题）
        while ((1 << offset) < desTo) {
            offset++;
        }
        return offset;
    }

    /**
     * 3. 将1,2两个步骤结合，生成等概率返回的[c,d]
     *
     * @param randBox {@link RandBox}
     * @param desFrom 目标起始值
     * @param desTo   目标结束值
     * @return [c, d]
     */
    public static int facade(RandBox randBox, int desFrom, int desTo) {
        int shiftNum = binaryShift(desTo);
        int sum;
        do {
            sum = 0;
            for (int i = 0; i < shiftNum; i++) {
                sum |= handleRandBox(randBox) << i;
            }
        } while (sum < desFrom || sum > desTo);
        return sum;
    }

    /**
     * 验证是否等概率返回0,1
     *
     * @param randBox {@link RandBox}
     */
    public static void verifyHandleRandBox(RandBox randBox) {
        int count = 0;
        for (int i = 0; i < TEST_COUNT; i++) {
            if (handleRandBox(randBox) == 1) {
                count++;
            }
        }
        System.out.printf("%s%n", ((double) count) / TEST_COUNT);
    }

    /**
     * 验证最大值所需的二进制的移位数量
     *
     * @param desMax 要求的值
     */
    public static void verifyBinaryShift(int desMax) {
        for (int i = 0; i < TEST_COUNT; i++) {
            int sum = 0;
            int rand = (int) (random() * desMax);
            int shiftNum = binaryShift(rand);
            for (int j = 0; j < shiftNum; j++) {
                sum |= 1 << j;
            }
            // 验证时，取[preSum, curSum];
            if (sum < rand && rand < sum - (1 << (shiftNum - 1))) {
                System.out.printf("%s%n %s%n %s%n %s%n %s%n",
                        "失败->",
                        "value: " + rand,
                        "shiftNum:" + shiftNum,
                        " sum:" + sum,
                        "preSum:" + (sum - (1 << (shiftNum - 1)))
                );
                break;
            }
            sum = 0;
        }

    }

    /**
     * 验证[a,b] -> [c,d]等概率
     *
     * @param randMin a
     * @param randMax b
     * @param desFrom c
     * @param desTo   d
     */
    public static void verifyFacade(int randMin, int randMax, int desFrom, int desTo) {
        RandBox randBox = new RandBox(randMin, randMax);

        int[] arr = new int[desTo - desFrom + 1];
        for (int i = 0; i < TEST_COUNT; i++) {
            arr[facade(randBox, desFrom, desTo) - desFrom]++;
        }
        for (int i = 0; i < arr.length; i++) {
            System.out.printf("%s%s%n", i + desFrom + ": ", (((double) arr[i]) / TEST_COUNT));
        }

    }

    /**
     *  zuo ------------------------------------------------------------------->
     */
    /**
     * 左神 - 利用[a,b]等概率返回0,1
     * <ul>
     *     <li>
     *         偶数情况可直接返回
     *     </li>
     *     <li>
     *         奇数情况判断
     *     </li>
     * </ul>
     *
     * @return [a, b]
     */
    private static int zuoHandleRandBox(RandBox randBox) {
        int min = randBox.min;
        int max = randBox.max;
        // 差大小
        int size = max - min + 1;
        // 奇数判断
        boolean odd = (size & 1) == 1;
        int middle = size / 2;
        int num;
        do {
            num = randBox.blackBoxAToB() - min;
        } while (odd && num == middle);
        // 01<2 -> 0  2和2比较是相等，所以23返回1，等概率

        return num < middle ? 0 : 1;


    }


    /**
     * 前提条件：from < to
     * [c,d]所需偏移位数
     *
     * @param from c
     * @param to   d
     * @return 偏移位数
     */
    private static int zuoBinaryShift(int from, int to) {
        int range = to - from;
        int num = 1;
        while ((1 << num) - 1 < range) {
            num++;
        }
        return num;
    }

    /**
     * 3. 将1,2两个步骤结合，生成等概率返回的[c,d]
     *
     * @param randBox {@link RandBox}
     * @param desFrom 目标起始值
     * @param desTo   目标结束值
     * @return [c, d]
     */
    private static int zuoFacade(RandBox randBox, int desFrom, int desTo) {

        int binaryShift = zuoBinaryShift(desFrom, desTo);
        int num;
        do {
            num = 0;
            for (int i = 0; i < binaryShift; i++) {
                num |= (zuoHandleRandBox(randBox) << i);
            }
        } while (num > (desTo - desFrom));
        return num + desFrom;

    }

    /**
     * 从[a,b] -> [c,d]中[c,d]等概率返回
     *
     * @param randBox {@link RandBox}
     * @return [c, d]
     */
    public static int f1ZuoDetailReturn(RandBox randBox) {
        int min = randBox.min;
        int max = randBox.max;
        // 差大小
        int size = max - min + 1;
        // 奇数判断
        boolean odd = (size & 1) == 1;
        int middle = size / 2;
        int num;
        do {
            num = randBox.blackBoxAToB() - min;
        } while (odd && num == middle);
        return num;
    }


    /**
     * 验证是否等概率返回0,1
     *
     * @param randBox {@link RandBox}
     */
    public static void verifyZuoHandleRandBox(RandBox randBox) {
        int count = 0;
        for (int i = 0; i < TEST_COUNT; i++) {
            if (zuoHandleRandBox(randBox) == 1) {
                count++;
            }
        }
        System.out.printf("%s%n", ((double) count) / TEST_COUNT);
    }

    /**
     * 验证[c,d]所需的二进制的移位数量
     *
     * @param desFrom c
     * @param desTo   d
     */
    public static void verifyZuoBinaryShift(int desFrom, int desTo) {
        for (int i = 0; i < TEST_COUNT; i++) {
            int sum = 0;
            int rand = (int) (random() * desTo);
            int shiftNum = zuoBinaryShift(desFrom, desTo);
            for (int j = 0; j < shiftNum; j++) {
                sum |= 1 << j;
            }
            // 验证时，取[preSum, curSum];
            if (sum < rand && rand < sum - (1 << (shiftNum - 1))) {
                System.out.printf("%s%n %s%n %s%n %s%n %s%n",
                        "失败->",
                        "value: " + rand,
                        "shiftNum:" + shiftNum,
                        " sum:" + sum,
                        "preSum:" + (sum - (1 << (shiftNum - 1)))
                );
                break;
            }
            sum = 0;
        }
    }

    /**
     * 验证[a,b] -> [c,d]等概率
     *
     * @param randMin a
     * @param randMax b
     * @param desFrom c
     * @param desTo   d
     */
    public static void verifyZuoFacade(int randMin, int randMax, int desFrom, int desTo) {
        int[] arr = new int[desTo - desFrom + 1];
        for (int i = 0; i < TEST_COUNT; i++) {

            arr[zuoFacade(new RandBox(randMin, randMax), desFrom, desTo) - desFrom]++;
        }
        for (int i = 0; i < arr.length; i++) {
            System.out.printf("%s%s%n", i + desFrom + ":", ((double) arr[i]) / TEST_COUNT);
        }
    }


    /**
     * 验证从[a,b] -> [c,d]中[c,d]是否等概率返回
     *
     * @param randBox {@link RandBox}
     * @return [c, d]
     */
    public static void verifyF1ZuoDetailReturn(RandBox randBox) {
        int min = randBox.min;
        int max = randBox.max;
        int[] arr = new int[max - min + 1];
        for (int i = 0; i < TEST_COUNT; i++) {
            arr[f1ZuoDetailReturn(randBox)]++;
        }
        for (int i : arr) {
            System.out.println(i);
        }
    }


    /**
     * 随机登概率返回[a,b]
     */
    public static class RandBox {
        int min;
        int max;

        public RandBox(int min, int max) {
            this.min = min;
            this.max = max;
        }

        /**
         * 黑盒函数：等概率返回[a,b]
         *
         * @return [a, b]
         */
        private int blackBoxAToB() {
            return ((int) (random() * (max - min + 1))) + min;
        }

        public void verifyBalckBoxAToB() {
            for (int i = 0; i < TEST_COUNT; i++) {
                int randNum = blackBoxAToB();
                if (min <= randNum && randNum <= max) {
                    continue;
                }
                System.out.println(randNum);
                break;
            }
        }
    }
}
